package 简单算法;

import java.util.Arrays;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-22
 * @Description: 给定一个未排序的整数数组，找到其中位数。
 * 中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。
 * 样例
 * 样例 1:
 * 输入：[4, 5, 1, 2, 3]
 * 输出：3
 * 解释：
 * 经过排序，得到数组[1,2,3,4,5]，中间数字为3
 * 样例 2:
 * 输入：[7, 9, 4, 5]
 * 输出：5
 * 解释：
 * 经过排序，得到数组[4,5,7,9]，第二个(4/2)数字为5
 * 挑战
 * 时间复杂度为O(n)
 * 注意事项
 * 数组大小不超过10000
 **/
public class 中位数 {

    public static void main(String[] args) {
        中位数 s = new 中位数();
        System.out.println(s.median(new int[]{4,5,1,2,3}));
    }

    public int median(int[] nums) {
        // write your code here
        int len = nums.length;
        Arrays.sort(nums);
        int index;
        if (len % 2 == 0) {
            index = (len / 2) - 1;
        } else {
            index = (len / 2);
        }
        return nums[index];
    }
}
